{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimizing Array After Replacing Pairs With Their Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minArrayLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将相邻元素相乘后得到最小化数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>，你可以对数组执行以下操作任意次数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择数组中的两个 <b>相邻</b>&nbsp;元素，例如&nbsp;<code>x</code>&nbsp;和&nbsp;<code>y</code>，使得&nbsp;<code>x * y &lt;= k</code>&nbsp;，并用一个值为&nbsp;<code>x * y</code>&nbsp;的 <b>单个元素</b>&nbsp;替换它们（例如，在一次操作中，数组&nbsp;<code>[1, 2, 2, 3]</code>，其中&nbsp;<code>k = 5</code> 可以变为&nbsp;<code>[1, 4, 3]</code>&nbsp;或&nbsp;<code>[2, 2, 3]</code>，但不能变为&nbsp;<code>[1, 2, 6]</code>）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>经过任意次数的操作后，&nbsp;</em><code>nums</code><em>&nbsp;的 <strong>最小</strong> 可能长度。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,3,7,3,5], k = 20\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们执行以下操作：\n",
    "1. [<u>2,3</u>,3,7,3,5] -&gt; [<u>6</u>,3,7,3,5]\n",
    "2. [<u>6,3</u>,7,3,5] -&gt; [<u>18</u>,7,3,5]\n",
    "3. [18,7,<u>3,5</u>] -&gt; [18,7,<u>15</u>]\n",
    "可以证明，在执行给定操作后，最小可能长度为3.</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3,3,3], k = 6\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>由于每两个相邻元素的乘积都大于 6，所以无法执行任何操作。因此，答案为 4。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>约束条件：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimizing-array-after-replacing-pairs-with-their-product](https://leetcode.cn/problems/minimizing-array-after-replacing-pairs-with-their-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimizing-array-after-replacing-pairs-with-their-product](https://leetcode.cn/problems/minimizing-array-after-replacing-pairs-with-their-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,3,7,3,5]\\n20', '[3,3,3,3]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        cur = 1\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            while r < n and cur * nums[r] <= k:\n",
    "                cur *= nums[r]\n",
    "                r += 1\n",
    "            if l == r:\n",
    "                ans += 1\n",
    "                l += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                ans += 1\n",
    "                cur = 1\n",
    "                l = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        if nums.count(0):\n",
    "            return 1\n",
    "        ans, y = 1, nums[0]\n",
    "        for x in nums[1:]:\n",
    "            if x * y <= k:\n",
    "                y *= x\n",
    "            else:\n",
    "                y = x\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "      if 0 in nums: return 1\n",
    "      res, sm = 0, k + 1\n",
    "      for i in nums:\n",
    "          if sm * i > k: sm, res = i, res + 1\n",
    "          else: sm *= i\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        res, sm = 1, nums[0]\n",
    "        for i in nums[1:]:\n",
    "            if i == 0: return 1\n",
    "            if sm * i > k: sm, res = i, res + 1\n",
    "            else: sm *= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        if 0 in nums: return 1\n",
    "        res, sm = 1, nums[0]\n",
    "        for i in nums[1:]:\n",
    "            if sm * i > k: sm, res = i, res + 1\n",
    "            else: sm *= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        if 0 in nums: return 1\n",
    "        res, sm = 0, k + 1\n",
    "        for i in nums:\n",
    "            if sm * i > k: sm, res = i, res + 1\n",
    "            else: sm *= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        if min(nums)==0: return 1\n",
    "        ans = len(nums)\n",
    "        cur = 1\n",
    "\n",
    "        for num in nums:\n",
    "            if cur*num<=k:\n",
    "                cur*=num\n",
    "                ans-=1\n",
    "            else:\n",
    "                cur=num\n",
    "            # print(num,cur,ans)\n",
    "        return ans+(nums[0]<=k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    把两个相邻的元素替换成它们的乘积，替换成它们的乘积\n",
    "    - 直到任意两个数乘起来都大于k\n",
    "    - 乘起来其实是subarray的问题，切分subarray，\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        temp = 1\n",
    "        res = l = 0\n",
    "        for i in nums:\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if temp * i > k:\n",
    "                temp = i\n",
    "                if l > 0:\n",
    "                    res += 1\n",
    "                l = 1\n",
    "            else:\n",
    "                temp *= i\n",
    "                l += 1\n",
    "        res += 1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        if min(nums)==0: return 1\n",
    "        ans = len(nums)\n",
    "        cur = 10**17\n",
    "\n",
    "        for num in nums:\n",
    "            if cur*num<=k:\n",
    "                cur*=num\n",
    "                ans-=1\n",
    "            else:\n",
    "                cur=num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        t=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if t*nums[i]>k:\n",
    "                t=nums[i]\n",
    "                res+=1\n",
    "            else:\n",
    "                t*=nums[i]\n",
    "        if t==0:return 1\n",
    "        return res+1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        tmp = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if tmp * nums[i] <= k:\n",
    "                tmp *= nums[i]\n",
    "                ans += 1\n",
    "            else:\n",
    "                tmp = nums[i]\n",
    "        return n - ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        ans, y = 1, nums[0]\n",
    "        for x in nums[1:]:\n",
    "            if x == 0:\n",
    "                return 1\n",
    "            if x * y <= k:\n",
    "                y *= x\n",
    "            else:\n",
    "                y = x\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        res, sm = 0, k + 1\n",
    "        for i in nums:\n",
    "            if i == 0: return 1\n",
    "            if sm * i > k: sm, res = i, res + 1\n",
    "            else: sm *= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "      if 0 in nums: return 1\n",
    "      res, sm = 0, k + 1\n",
    "      for i in nums:\n",
    "          if sm * i > k: sm, res = i, res + 1\n",
    "          else: sm *= i\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        ans=n=len(nums)\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]*nums[i-1]<=k:\n",
    "                ans-=1\n",
    "                nums[i]=nums[i]*nums[i-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        s = 1\n",
    "        ans = 0\n",
    "        c = 0\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        for i in range(len(nums)):\n",
    "            s = s*nums[i]\n",
    "            if s > k:\n",
    "                s = nums[i] \n",
    "                if c:    \n",
    "                    ans += 1\n",
    "                c = 1\n",
    "            else:\n",
    "                c += 1\n",
    "        \n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        cnt = 0\n",
    "        prev = 1\n",
    "        cache = 0\n",
    "        for k1,v in enumerate(nums):\n",
    "            peek = prev * v\n",
    "            if peek <= k:\n",
    "                cache += 1\n",
    "                prev = peek\n",
    "            else:\n",
    "                if cache > 0:\n",
    "                    cnt += cache - 1\n",
    "                cache = 1\n",
    "                prev = v\n",
    "        if cache > 0:\n",
    "            cnt += cache - 1\n",
    "        return len(nums) - cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if 0 in nums:\n",
    "            return 1\n",
    "        cnt = 0\n",
    "        prev = 1\n",
    "        cache = 0\n",
    "        for k1,v in enumerate(nums):\n",
    "            peek = prev * v\n",
    "            if peek <= k:\n",
    "                cache += 1\n",
    "                prev = peek\n",
    "            else:\n",
    "                if cache > 0:\n",
    "                    cnt += cache - 1\n",
    "\n",
    "                cache = 1\n",
    "                prev = v\n",
    "        if cache > 0:\n",
    "            cnt += cache - 1\n",
    "        return len(nums) - cnt\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.minArrayLength(nums = [3,3,3,3], k = 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        stack = []\n",
    "        for x in nums:\n",
    "            while stack and stack[-1] * x <= k:\n",
    "                x *= stack.pop()\n",
    "            stack.append(x)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        stack = []\n",
    "        for v in nums:\n",
    "            if v==0:\n",
    "                return 1\n",
    "            if stack and stack[-1]*v<=k:\n",
    "                stack.append(stack.pop()*v)\n",
    "            else:\n",
    "                stack.append(v)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minArrayLength(self, nums: List[int], k: int) -> int:\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            stack.append(num)\n",
    "            while len(stack) >= 2 and stack[-1] * stack[-2] <= k:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                stack.append(a * b)\n",
    "        return len(stack)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
